Greatest Common Divisor of Strings

1071. Greatest Common Divisor of Strings

題目敘述

兩個字串s和t。定義s可以被t整除為s = t + t + t + .....，即s只由數個t組成。
題目將給定兩個字串str1與str2，找出最大的公因字串x，使得x為最長且可以同時整除str1與str2。
str1與str2只包含大寫的英文字母。
題目原文與所給的範例及限制如下:

解題思路

• 先判斷這兩個字串存不存在公因字串x。判斷方法為直接把兩個字串合在一起，然後再把順序倒過來合在一起。如果這兩個合成的字串相等的話，代表有公因字串。反之，不相等就代表沒有公因字串，代表沒有共同重複的子字串。
• 本題使用遞迴的寫法找最大公因字串，做法跟找最大公因數很像。
• 可以被整除的子字串長度一定是母字串的因數，所以可以把這題想成是找最大公因數的題目。
• 題目下方有提示說最大公因字串一定是從兩個字串的開頭開始，因此return的時候是從題目字串的頭開始，直到兩個字串長度的最大公因數。

程式碼

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        def gcd(x, y):
            if y == 0:
                return x
            else:
                return gcd(y, x%y)
        return str1[:gcd(len(str1), len(str2))]